题解 CF780F 【Axel and Marston in Bitland】

发表于 | 更新于

给定一张有向图(可能有自环，保证没有重边)，每条边有两种类型，分别为$1$或者$0 $从$1$开始走，要求走过的路径类型成如下方式

$0$

$01$

$0110$

$01101001$

第$i$个是由第$i -1$个和第$i - 1$个取反拼在后面。 求最长路。

题目要求第$i$个是由第$i-1$个和（第$i-1$个取反）拼在后面。 求最长路。

因此可以用倍增的思想进行$dp$，$dp$思路在代码中。可以用$bitset$优化

最后选取时从长的往短的枚举，在加的过程中大于$1e18$就退出

听说好像可以用矩乘优化，但蒟蒻我不会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
bitset<505>f[2][65][505],t,pre;//f[p][s][x][y]表示第一条边为p类型，x与y之间有2的s次方的路径存不存在
ll ans;
int main(){
    int n=read(),m=read();
    while (m--){
        int x=read(),y=read(),t=read();
        f[t][0][x][y]=1;
    }
// 转移方程:f[p][s][x][y]|=(f[p][s][x][k]&f[p^1][s][k][y])     k为枚举的中转点 
//最后一位可以用bitset压掉，即if (f[p][s-1][x][k]) f[p][s][x]|=f[p^1][s-1][k]
    for (int s=1;s<=60;++s)//s为路径长度是2的多少幂次 
        for (int p=0;p<=1;++p)//p为第一条边的类型 
            for (int x=1;x<=n;++x)//x为起点 
                for (int k=1;k<=n;++k)//k为枚举的中转点 
                    if (f[p][s-1][x][k])    
                        f[p][s][x]|=f[p^1][s-1][k];
    for (int i=1;i<=n;++i)
        if (f[0][60][1][i]){
            puts("-1");return 0;
        }
    int now=0;pre[1]=1;//一开始只有节点1可以作为起点 
    for (int s=59;s>=0;--s){// 贪心得选，能选长的就选长的 
        t.reset();
        for (int i=1;i<=n;++i)
            if (pre[i])//pre数组表示当前可不可以选为起点 
                t|=f[now][s][i];//t数组表示从当前可选的起点走接下来能到达的点
        if (t.count()){
            pre=t;
            now^=1;
            ans+=(1ll<<s);
            if (ans>1e18){puts("-1");return 0;}
        }
    }
    printf("%I64d",ans);
}